//
//$Id: sets.cpp 679 2011-03-12 16:50:06Z andrew.tsyganov $
#include "stdafx.h"
#include "include/fa.h"
#include "include/sets.h"
#include "include/utils.h"
#include <algorithm>

using namespace std;

///////////////////////////////////////////////////////////////////////
// BitSet /////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////
u_t BitSet::get_By_Count(u_t const i) const
{
    u_t k = 0;
    u_t j = get_first();
    do
    {
        if (k == i)
		{
            return j;
		}
        ++k;
        j = get_next(j);
    }
    while (j);

#ifdef _MSC_VER
    __assume(0);
#endif
}

IntSet BitSet::to_IntSet() const
{
	IntSet is;
	for (BitSet::enumerator en = (*this).first(); en != (*this).end(); ++en)
	{
		is.insert(*en);
	}

	return is;
}


string BitSet::to_String(Brackets_Type const bt, int const add) const
{
    if (empty())
    {
        return OpenBracket(bt) + CloseBracket(bt);
    }

    string s = OpenBracket(bt);

    for (BitSet::enumerator en = first(); en != end(); ++en)
    {
        s += IntToString(*en + add) + ",";
    }

    s.erase(s.length()-1);
    s += CloseBracket(bt);

    return s;
}

string BitSet::to_String(string const& pfx, Brackets_Type const bt, Labels_Type const lt, int const add) const
{
    if (empty())
    {
        return OpenBracket(bt) + CloseBracket(bt);
    }

    string s = OpenBracket(bt);

    for (BitSet::enumerator en = first(); en != end(); ++en)
    {
        s += MakeLabel(pfx, *en + add, lt) + ",";
    }

    s.erase(s.length()-1);
    s += CloseBracket(bt);

    return s;
}

unsigned char* BitSet::serialize(BitSet_Serializer& ss, unsigned& len) const
{
    //optimize();  
    BitSet::statistics st;
    calc_stat(&st);
    unsigned char* buf = new unsigned char[st.max_serialize_mem];
    len = ss.serialize((*this), buf, 0);

    return buf;
}

u_t BitSet::calc_Hash() const
{
	u_t max = sizeof(u_t) << 3;
    u_t res = 0;

	for (BitSet::enumerator en = first(); en != end(); ++en)
	{
		if (*en >= max)
		{
			break;
		}

		res += 1 << *en;
	}

    return res;
}

BitSet operator |(BitSet const& lhs, BitSet const& rhs) 
{ 
    BitSet res = lhs; 
    res |= rhs; 
    return res; 
};

BitSet operator &(BitSet const& lhs, BitSet const& rhs) 
{ 
    BitSet res = lhs; 
    res &= rhs; 
    return res; 
};

BitSet operator -(BitSet const& lhs, BitSet const& rhs) 
{ 
    BitSet res = lhs; 
    res -= rhs; 
    return res; 
};

bool operator <=(BitSet const& lhs, BitSet const& rhs) 
{ 
    if (lhs.count() > rhs.count()) 
    {
        return false; 
    }
    
    for (BitSet::enumerator en = lhs.first(); en != lhs.end(); ++en)
    {
        if (!rhs.contains(*en))
        {
            return false;
        }
    }

    return true;
}

///////////////////////////////////////////////////////////////////////
// IntSet /////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////
void IntSet::insert_range(u_t left, u_t right, bool value)
{
	if (value)
	{
		for (u_t i = left; i <= right; ++i)
		{
			insert(i);
		}
	}
	else
	{
		for (u_t i = left; i <= right; ++i)
		{
			remove(i);
		}
	}
}

u_t IntSet::get_By_Count(u_t const i) const
{
	u_t k = 0;
	for (Subset::const_iterator it = begin(); it != end(); ++it)
	{
		if (k == i)
		{
			return *it;
		}
		++k;
	}

	return *rbegin();
}

void IntSet::operator |=(IntSet const& is)
{
	// acceptable performance
	insert(is.begin(), is.end());
}

void IntSet::operator &=(IntSet const& is)
{
    // slower ???
	IntSet res;
	set_intersection(this->begin(), this->end(), is.begin(), is.end(), inserter(res, res.begin()));
	*this = res;
/*
	// faster ???
	IntSet::iterator it1 = (*this).begin();
	IntSet::const_iterator it2 = is.begin();

	while ((it1 != (*this).end()) && (it2 != is.end())) 
	{    
		if (*it1 < *it2) 
		{
			(*this).erase(it1++);
		} 
		else 
		{
			if (*it2 < *it1) 
			{
				++it2;
			} 
			else 
			{ // the case *it1 == *it2
				++it1;
				++it2;
			}
		}
    }
    // Anything left in set_1 from here on did not appear in set_2,
	// so we remove it.
	(*this).erase(it1, (*this).end());
*/
}

void IntSet::operator -=(IntSet const& is)
{
	// slower ???
	IntSet res;
	set_difference(this->begin(), this->end(), is.begin(), is.end(), inserter(res, res.begin()));
	*this = res;
/*
	// faster ???
	IntSet::iterator it1 = (*this).begin();
	IntSet::const_iterator it2 = is.begin();

	while ((it1 != (*this).end()) && (it2 != is.end()))
	{
		if (*it1 < *it2) 
		{
			++it1;
		} 
		else 
		{
			if (*it2 < *it1) 
			{
				++it2;
			} 
			else 
			{
				(*this).erase(it1++);
				++it2; 
			}
		}
	}
*/
}

void IntSet::serialize(unsigned char* buf, unsigned& len) const
{
	unsigned n = (unsigned) size();
	len = (n + 1) * sizeof(u_t);
	unsigned* p = (unsigned*) buf;

	*p++ = n;
	for (IntSet::const_iterator it = begin(); it != end(); ++it)
	{
		*p++ = (unsigned) *it;
	}
}

unsigned char* IntSet::serialize(unsigned& len) const
{
	unsigned n = (unsigned) size();
	len = (unsigned) (n + 1) * sizeof(u_t);

	unsigned char* buf = new unsigned char[len];
	unsigned* p = (unsigned*) buf;

	*p++ = n;
	for (IntSet::const_iterator it = begin(); it != end(); ++it)
	{
		*p++ = (unsigned) *it;
	}

	return buf;
}

void IntSet::deserialize(unsigned char const* buf)
{
	if (size() > 0)
	{
		clear();
	}

	unsigned* p = (unsigned*) buf;
	u_t n = (u_t) *p++;
	for (u_t i = 0; i < n; ++i)
	{
		insert((u_t) *p++);
	}
}

BitSet IntSet::to_BitSet() const
{
	BitSet bs;
	for (IntSet::const_iterator it = begin(); it != end(); ++it)
	{
		bs.insert(*it);
	}

	return bs;
}


string IntSet::to_String(Brackets_Type const bt, int const add) const
{
    if (empty())
    {
        return OpenBracket(bt) + CloseBracket(bt);
    }

    string s = OpenBracket(bt);

	for (IntSet::const_iterator it = begin(); it != end(); ++it)
    {
        s += IntToString(*it + add) + ",";
    }

    s.erase(s.length()-1);
    s += CloseBracket(bt);

    return s;
}

string IntSet::to_String(string const& pfx, Brackets_Type const bt, Labels_Type const lt, int const add) const
{
    if (empty())
    {
        return OpenBracket(bt) + CloseBracket(bt);
    }

    string s = OpenBracket(bt);

	for (IntSet::const_iterator it = begin(); it != end(); ++it)
    {
        s += MakeLabel(pfx, *it + add, lt) + ",";
    }

    s.erase(s.length()-1);
    s += CloseBracket(bt);

    return s;
}

u_t IntSet::calc_Hash() const
{
	u_t max = sizeof(u_t) << 3;

    u_t res = 0;
	
	for (IntSet::const_iterator it = begin(); it != end(); ++it)
	{
		if (*it >= max)
		{
			return res;
		}

		res += 1 << *it;
	}

    return res;
}

bool operator ==(IntSet const& lhs, IntSet const& rhs)
{
	u_t n1 = lhs.size();
	u_t n2 = rhs.size();

	if (n1 != n2)
	{
		return false;
	}

	if ((n1 == 0) && (n2 == 0))
	{
		return true;
	}

	return equal(lhs.begin(), lhs.end(), rhs.begin());
}

bool operator <=(IntSet const& lhs, IntSet const& rhs)
{
	u_t n1 = lhs.size();
	u_t n2 = rhs.size();

	if (n1 > n2)
	{
		return false;
	}

	if (n1 == 0)
	{
		return true;
	}

	return includes(rhs.begin(), rhs.end(), lhs.begin(), lhs.end());
}

// ---------------------------------------------------------------

// Find empty set in a vector of sets
// input:  vs - vector of sets 
// output: id of the empty set (size of the vector if the empty set was not found)
u_t FindEmptySet(vector<Subset> const& vs)
{
	u_t n = vs.size();
	u_t empty_id = n;
	for (u_t i = 0; i < n; ++i)
	{
		if (vs[i].empty())
		{
			empty_id = i;
			break;
		}
	}

	return empty_id;
}

u_t FindEmptySet(vector<Subset> const& vs1, vector<Subset> const& vs2)
{
	u_t n = vs1.size();
	u_t empty_id = n;
	for (u_t i = 0; i < n; ++i)
	{
		if (vs1[i].size() == 1)
		{
			if (vs2[*(vs1[i].begin())].empty())
			{
				empty_id = i;
				break;
			}
		}
	}

	return empty_id;
}

bool FindInVector(vector<BitSet> const& vbs, BitSet const& bs, u_t& id)
{
    for (u_t i = 0; i < vbs.size(); ++i)
    {
        if (vbs[i] == bs)
        {
            id = i;
            return true;
        }
    }

    return false;
}

void PrintVector(ostream& os, vector<BitSet> const& vbs)
{
    for (u_t i = 0; i < vbs.size(); ++i)
    {
        os << vbs[i].to_String() << " ";
    }
    os << endl;
}


//EOF!
